/*
 * @lc app=leetcode.cn id=214 lang=typescript
 *
 * [214] 最短回文串
 */

// @lc code=start
function shortestPalindrome(s: string): string {
  let revs = s.split('').reverse().join('');
  // 将原字符串和反转后的串用一个特殊符号拼接
  // 用KMP去找这个新串的最长相同前后缀
  revs = s + '#' + revs;

  const n = revs.length;
  const next = new Array(n).fill(-1);
  let j = -1;
  for (let i = 1; i < n; i++) {
    // 如果有公共前后缀，就跳转
    while (j !== -1 && revs[i] !== revs[j + 1]) {
      j = next[j];
    }
    if (revs[i] === revs[j + 1]) {
      j++;
    }
    next[i] = j;
  }
  // 拿到去掉公共前缀的字符串
  revs = revs.substring(next[n - 1] + 1, s.length);
  revs = revs.split('').reverse().join('');
  return revs + s;
}
// @lc code=end
